1. Field of the Invention
This invention relates to automated systems for image detection and, more specifically, to a computer-implemented procedure for extracting lines from an image data field.
2. Discussion of the Related Art
In two-dimensional images containing man-made objects, grey-level discontinuities that lie along straight lines abound. Examples include such things as manufactured parts, buildings, aerial photographs of towns and road systems and so forth. Accordingly, the automated detection of straight lines in a two-dimensional image is a fundamentally important function of artificial vision systems.
The line detection problem is recognized in part as a problem of establishing meaningful groups of edge points that lie along straight lines. The Hough transform is a well-known method in the art for detecting edge points that satisfy a collinearity constraint. The Hough transform is limited to examination of the collinearity of image points. The distribution of such points along a line is not considered. Although this feature makes the Hough transform insensitive to missing edge points and occlusions, the lack of such proximity constraints often leads to errors when processing complex images. The simplest improved approach in the art merely adds the proximity requirement as a post-processing step in the Hough transformation procedure. However, the proper measure of the resulting proximity constraint is an open question in such a simple augmented Hough transform procedure. It is generally accepted that the proximity constraint should be a function of feature size; that is, the length of the lines detected.
Practitioners in the art have suggested more sophisticated and efficient methods for finding straight lines in edge maps using the Hough transform. For instance, John Princen, et al ("A Hierarchical Approach To Line Extraction Based on the Hough Transform", Computer Vision, Graphics and Image Processing, October 1990, Vol. 52, No. 1, pp. 57-77) teach a modified Hough transform procedure based on a pyramid structure with each layer in the pyramid splitting the complete image into a number of subimages. At the bottom level of the pyramid, short line segments are detected by applying a Hough transform to small subimages. The procedure then progresses from the bottom up by grouping small line segments into longer lines. Line segments having local support propagate up the hierarchy and participate in higher level groupings. The length of the line detection determines the pyramid level to which it propagates. However, the Princen, et al procedure offers no particular method for improving line detection in noisy images.
The difficulties introduced into the edge detection problem by image noise fields are well-known in the art and have been addressed by other practitioners. For instance, L. E. Nordell, et al ("An Adaptive Operator Set", Proceedings of the Fifth International Conference on Pattern Recognition, Miami Beach, Fla., U.S.A., 01-04 December 1980, IEEE, New York, pp. 1304-1307) introduce a complementary method for handling the segmentation problem for line detection using sets of direction-dependent filters. They suggest that the problem may be converted to a homogeneity determination problem by defining lines and edges as transitions between homogeneous regions of the image. They teach the use of an adaptive process that selects the proper transform operator according to the degree of local homogeneity in the image. Their selected operator forms part of a larger set of operators that have application to structured image processing. One such operator discussed by Nordell, et al assigns to every pixel a complex value representing the direction and magnitude of the corresponding edges. Different operator sizes are assigned to different areas of the image to optimized edge detection without blurring.
Also, V. S. Alagar, et al ("Algorithms for Detecting M-Dimensional Objects in N-Dimensional Spaces", IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-3, No. 3, pp. 245-256, May 1981) consider another solution to the noisy-image edge detection problem. They propose transform methods and notions of probability measures governing the parameters of transforms for the case of uniformly distributed noise within an image space. They suggest that different quantization schemes for the transformed space are desirable for different probablistic assumptions for noise and also extend the two-dimensional line detection problem to general N-dimensional space. Alagar, et al introduce three measures of robustness (precision, recall and goodness ) to describe the effectiveness of various line detection procedures when applied to noisy images. Their evaluations are based on the generalized Duda-Hart procedure known in the art, which uses the normal parameters (r, .theta.) to specify line. The Duda-Hart improvement over the Hough transform permits line detection by cluster detection in r-.theta. space but is replete with inaccuracies and limitations, including ambiguities in r-.theta. cell membership. Alagar, et al examine the generalized Duda-Hart procedure in detail and also evaluate several improvements suggested by other practitioners in the art. However, Alagar, et al do not themselves suggest a solution to the general ambiguity problem associated with the Duda-Hart line-segment point mapping procedures.
The art of manipulating multivariate relationships of multi-dimensional data is unrelated to the image detection art and is generally associated with methods for representing N-dimensional events such as air traffic control scenarios, hypersurfaces and the like. For instance, Alfred Inselberg, et al ("Parallel Coordinates for Multi-Dimensional Graphics", National Computer Graphics Association Conference, Philadelphia, Pa., 22-26 March 1987, Vol. 3, pp. 547-566) demonstrate the application of a Cartesian-coordinate to parallel-coordinate transform to the air traffic control display problem. Their paper is entirely incorporated herein by this reference. The concept of parallel coordinates was first introduced circa 1985 for use in multivariate displays and graphics. Until now, the parallel coordinate transform has not been applied to automated line detection or vision system procedures.
The notion of image point neighborhoods is known to be useful in detecting points in noisy images. However, this notion cannot be readily extended to "line neighborhoods" because of an inherent ambiguity for such neighborhoods in normal coordinate systems leading to unacceptable "false line" detections. Because of this inherent ambiguity problem known in the art, there exists a clearly-felt need for a nonambiguous line-to-point transform method for edge detection in noisy images. The related unresolved problems and deficiencies are clearly felt in the art and are solved by this invention in the manner described below.